#include <iostream>
#include <algorithm>
#include <vector>
#include "conio.h"

using namespace std;

template<class T> class Heap
{
public:
	Heap(const vector<T> &arr)
	{
		heap_arr = arr;
		for (int i = static_cast<int>(arr.size() / 2); i >= 0 ; --i)
		{
			max_heapify(i);
		}
	}

	vector<T> heap_sort_1()
	{
		vector<T> res(heap_arr.size()),
			heap_arr_copy = heap_arr;

		res[0] = get_max();
		for (int i = 1; i < static_cast<int>(res.size()); ++i)
		{
			heap_arr[0] = heap_arr[heap_arr.size()-1];
			heap_arr.resize(heap_arr.size()-1);
			max_heapify(0);
			res[i] = get_max();
		}

		heap_arr = heap_arr_copy;
		return res;
	}

	vector<T> heap_sort_2()
	{
		vector<T> res(heap_arr.size()),
			heap_arr_copy = heap_arr;

		for (int i = 0; i < static_cast<int>(res.size()); ++i)
		{
			res[i] = extract_max();
		}

		heap_arr = heap_arr_copy;
		return res;
	}

	void insert(T elem)
	{
		heap_arr.resize(heap_arr.size()+1);
		int elem_idx = heap_arr.size()-1,		
			parent_idx = elem_idx / 2;

		heap_arr[elem_idx] = elem;
		while (elem_idx > 0 && heap_arr[parent_idx] < heap_arr[elem_idx])
		{
			swap(heap_arr[parent_idx], heap_arr[elem_idx]);
			elem_idx = parent_idx;
			parent_idx = elem_idx / 2;
		}
	}

	T get_max() const
	{
		if (heap_arr.size() <= 0)
			throw string("Heap does not have elements");

		return heap_arr[0];
	}

	T extract_max()
	{
		if (heap_arr.size() <= 0)
			throw string("Could not extract max because heap is empty");

		T res = heap_arr[0];
		heap_arr[0] = heap_arr[heap_arr.size()-1];
		heap_arr.resize(heap_arr.size()-1);
		max_heapify(0);
		return res;
	}

	int get_size() const
	{
		return heap_arr.size();
	}

	void set_size(int s)
	{
		heap_arr.resize(s);
	}

	T& get_elem(int i)
	{
		return heap_arr[i];
	}

private:
	void max_heapify(int idx)
	{
		int l = idx * 2,
			r = idx * 2 + 1,
			largest = idx;

		if (l < heap_arr.size() && heap_arr[idx] < heap_arr[l])
			largest = l;
		
		if (r < heap_arr.size() && heap_arr[largest] < heap_arr[r])
			largest = r;

		if (largest != idx)
		{
			swap(heap_arr[idx], heap_arr[largest]);
			max_heapify(largest);
		}
	}

	vector<T> heap_arr;
};

struct Triplet
{
	Triplet() {}
	Triplet(int v, int s, int i) : value(v), seq_num(s), index(i) {}

	int value, seq_num, index;
	
	bool operator< (const Triplet &a) const
	{
		if (value < a.value)
			return true;
		else if (value > a.value)
			return false;

		if (seq_num < a.seq_num)
			return true;
		else if (seq_num > a.seq_num)
			return false;

		if (index < a.index)
			return true;
		else if (index > a.index)
			return false;

		return false;
	}
};

vector<int> merge_sequences(const vector<vector<int>> &seqs)
{
	vector<int> res(seqs.size() * seqs[0].size());
	vector<Triplet> cur_max_candidates(seqs.size());

	for (int i = 0; i < seqs.size(); ++i)
		cur_max_candidates[i] = Triplet(seqs[i][0], i, 0);

	Heap<Triplet> h(cur_max_candidates);
	int i = 0;
	while (i < seqs.size() * seqs[0].size())
	{
		Triplet cur_elem_to_insert = h.extract_max();
		res[i] = cur_elem_to_insert.value;

		if (cur_elem_to_insert.index + 1 < seqs[0].size())
		{
			Triplet nex_elem(seqs[cur_elem_to_insert.seq_num][cur_elem_to_insert.index+1], cur_elem_to_insert.seq_num, 
				cur_elem_to_insert.index+1);
			h.insert(nex_elem);
		}
		++i;
	}

	return res;
}

void main()
{
// 	int n_elems;
// 	cout << "Input number of elements : " << endl;
// 	cin >> n_elems;
// 
// 	vector<int> arr(n_elems);
// 	cout << "Input elements : " << endl;
// 	for (int i = 0; i < n_elems; ++i)
// 		cin >> arr[i];
// 
// 	Heap h(arr);
// 	cout << "Maximal element in array : " << h.get_max() << endl;
// 	cout << "Sorted array (heap_sort_1):" << endl;
// 	vector<int> sorted = h.heap_sort_1();
// 	for (int i = 0; i < sorted.size(); ++i)
// 		cout << sorted[i] << " ";
// 	cout << endl;
// 
// 	cout << "Sorted array (heap_sort_2):" << endl;
// 	sorted = h.heap_sort_2();
// 	for (int i = 0; i < sorted.size(); ++i)
// 		cout << sorted[i] << " ";
// 	cout << endl;
// 
// 	h.insert(100);
// 	cout << "Sorted array after insertion (heap_sort_2):" << endl;
// 	sorted = h.heap_sort_2();
// 	for (int i = 0; i < sorted.size(); ++i)
// 		cout << sorted[i] << " ";
// 	cout << endl;

	int n_sequences, seq_size;
	cout << "Input number of sequences:" << endl;
	cin >> n_sequences;
	cout << "Input sequence size:" << endl;
	cin >> seq_size;

	vector<vector<int>> seqs(n_sequences);
	for (int i = 0; i < n_sequences; ++i)
	{
		seqs[i].resize(seq_size);
		cout << endl << "Input sequence #" << i << ":" << endl;
		for (int j = 0; j < seq_size; ++j)
		{
			cin >> seqs[i][j];
		}
	}

	vector<int> merged = merge_sequences(seqs);
	cout << "Merged sequences:" << endl;
	for (int i = 0; i < merged.size(); ++i)
		cout << merged[i] << " ";

	_getch();
}